﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

using System.IO;
using System.Threading.Tasks;

using Microsoft.SolverFoundation.Services;
using Microsoft.SolverFoundation.Common;
 using System.Collections;

namespace TesteC
{ 
    class Node
    {
        public int level;
        public int profit;
        public int weight;
        public decimal bound;
        public string path;


        public Node()
        {

        }
        public Node(Node nodeToCopy)
        {
            level = nodeToCopy.level;
            profit = nodeToCopy.profit;
            weight = nodeToCopy.weight;
            bound = nodeToCopy.bound;
            path = nodeToCopy.path;
        }
    }

    class Item
    {
        public int id;
        public int profit;
        public int weight;
        public float worthRatio;
        public string isTaken;
    }

   

    class Program
    {
        static public string debugInfo = "";
        static int bestPossibleValue;

        static public Node bestNode;

        static void Main(string[] args)
        {
            /*
            DirectoryInfo d = new DirectoryInfo(@"C:\dev\coursera\knapsack\data");
            FileInfo[] fs = d.GetFiles();
            for (int i = 0; i < fs.Length; i++)
            {
                FileInfo f = fs[i];

                curFile = f.FullName;
                doSolve(f.FullName);
            }
            */
            doSolve("tmp.data");
            //doSolve("C:/dev/coursera/knapsack/data/ks_4_0");
            //doSolve("C:/dev/coursera/knapsack/data/ks_19_0");
            //doSolve("C:/dev/coursera/knapsack/data/problem4");
            //doSolve("C:/dev/coursera/knapsack/data/problem6"); //wanted  : 1099870 Max possible : 1099893
                                                               // 
            /*
            if (args.Length != 0)
            {
                doSolve("tmp.data");
            }
            else
            {
                //doSolve("C:/dev/coursera/knapsack/data/ks_4_0");
                doSolve("C:/dev/coursera/knapsack/data/ks_10000_0");
                doSolve("C:/dev/coursera/knapsack/data/ks_19_0");
            }
             */


            

            //doSolve("C:/dev/coursera/graphColoring/GraphColoringC#/Knapsack/bin/Debug/data/gc_4_1");
            //doSolve("C:/dev/coursera/graphColoring/GraphColoringC#/Knapsack/bin/Debug/data/gc_20_1");
            //doSolve("C:/dev/coursera/graphColoring/GraphColoringC#/Knapsack/bin/Debug/data/gc_20_3");
          //  doSolve("C:/dev/coursera/graphColoring/GraphColoringC#/Knapsack/bin/Debug/data/gc_20_5");
            //doSolve("C:/dev/coursera/graphColoring/GraphColoringC#/Knapsack/bin/Debug/data/gc_50_1");
           // doSolve("C:/dev/coursera/graphColoring/GraphColoringC#/Knapsack/bin/Debug/data/gc_50_3");
           // doSolve("C:/dev/coursera/graphColoring/GraphColoringC#/Knapsack/bin/Debug/data/gc_50_5");
           // doSolve("C:/dev/coursera/graphColoring/GraphColoringC#/Knapsack/bin/Debug/data/gc_50_7");
           //doSolve("C:/dev/coursera/graphColoring/GraphColoringC#/Knapsack/bin/Debug/data/gc_70_1");
            //doSolve("C:/dev/coursera/graphColoring/GraphColoringC#/Knapsack/bin/Debug/data/gc_100_1");
            
            
        }
        private static int CompareItemsWorth(Item x, Item y)
        {
            return y.worthRatio.CompareTo(x.worthRatio);
        }

        private static int CompareId(Item x, Item y)
        {
            return x.id.CompareTo(y.id);
        }

        static void doSolve(string file)
        {
            int maxProfit;
            int n = 4;
            int W = 16;
            int[] w = new int[]{1,2,3,4};
            int[] p = new int[]{2,3,4,5};
            GetData(file, out n, out W, out w, out p);
            Item[] itemList = FillDataStructure(n, w, p);
            Array.Sort(itemList, CompareItemsWorth);

            maxProfit = knapsack(n, itemList, W);

            

            //6, wanted  : 1099870 Max possible : 1099893
            bestPossibleValue = bestPossibleValue;
            string[] nodes = bestNode.path.Split(' ');
            List<string> answer = nodes.ToList();
            answer.Add("1");
            while (answer.Count <= n)
            {
                answer.Add("0");
            }
            for(int i = 0; i < answer.Count() - 1; i++)
            {
                itemList[i].isTaken = answer[i + 1];
            }

            Array.Sort(itemList, CompareId);
            string marc = answer[0];
            for(int i = 1; i < itemList.Length; i++)
            {
                marc += " " + answer[i];
            }

            int totValue = 0;
            int totWeight = 0;
            string output = "";

            output = bestNode.profit + " 1\n";
            output += itemList[0].isTaken;
            for (int i = 1; i < itemList.Length; i++ )
            {
                totValue += itemList[i].isTaken == "1" ? itemList[i].profit : 0;
                totWeight += itemList[i].isTaken == "1" ? itemList[i].weight : 0;
                output += " " + itemList[i].isTaken;
            }
                //string[] answerArray = answer.ToArray();
                //string finalAnswer = String.Join(" ", answerArray);
                //finalAnswer = finalAnswer.Remove(0, 1);


                //System.Diagnostics.Debug.Write(bestNode.profit + " 0\n");
            //System.Diagnostics.Debug.Write(marc);

            using (StreamWriter sw = new StreamWriter("resp.txt"))
            {
                sw.WriteLine(output);
            }
        }

        private static Item[] FillDataStructure(int n, int[] w, int[] p)
        {
            Item[] itemList = new Item[n];
            for(int i = 0; i < n; i++)
            {
                Item curItem = new Item();
                curItem.id = i;
                curItem.weight = w[i];
                curItem.profit = p[i];
                curItem.worthRatio = (float)p[i] / (float)w[i];
                itemList[i] = curItem;
            }
            return itemList;
        }

        static decimal bound(Node u, int n, int W, Item[] itemList)
        {
            int j = 0, k = 0;
            int totweight = 0;
            decimal result = 0;

            if (u.weight >= W)
            {
                return 0;
            }
            else
            {
                result = u.profit;
                j = u.level + 1;
                totweight = u.weight;

                while ((j < n) && (totweight + itemList[j].weight <= W))
                {
                    totweight = totweight + itemList[j].weight;
                    result = result + itemList[j].profit;
                    j++;
                }

                k = j;

                if (k < n)
                {
                    decimal d1 = W - totweight;
                    decimal d2 = (decimal)itemList[k].profit / (decimal)itemList[k].weight;
                    
                    //d2 = Math.Max(0.0001F, d2);
                    //d2 = Math.Min(0.9999F, d2);

                    result = result + d1 * d2;
                    //result = 1099893;// result + d1 * d2;
                }
                return result;
            }
        }
        static void GetBestPossibleValueForBound(int aNbItems, int aCapacity, int[] aValues, int[] aWeight)
        {
            // Input:
            // Values (stored in array v)
            // Weights (stored in array w)
            // Number of distinct items (n)
            // Knapsack capacity (W)


            // for w from 0 to W do
            //  m[0, w] := 0
            //end for 
            //for i from 1 to n do
            //  for j from 0 to W do
            //    if j >= w[i] then
            //      m[i, j] := max(m[i-1, j], m[i-1, j-w[i]] + v[i])
            //    else
            //      m[i, j] := m[i-1, j]
            //    end if
            //  end for
            //end for

            int[,] m = new int[2, aCapacity + 1];

            for (int w = 0; w < aCapacity; w++)
            {
                m[0, w] = 0;
            }

            for (int i = 1; i <= aNbItems; i++)
            {
                for (int j = 0; j <= aCapacity; j++)
                {
                    if (j >= aWeight[i - 1])
                    {
                        m[1, j] = Math.Max(m[0, j], m[0, j - aWeight[i - 1]] + aValues[i - 1]);
                    }
                    else
                    {
                        m[1, j] = m[0, j];
                    }
                }
                for (int j = 0; j <= aCapacity; j++)
                {
                    m[0, j] = m[1, j];
                }
            }

            bestPossibleValue = m[0, aCapacity];
        }
        static int knapsack(int n, Item[] itemList, int W)
        {
            Queue<Node> Q = new Queue<Node>();
            Node u = new Node();
            Node v = new Node();

            Q.Clear();
            v.level = -1;
            v.profit = 0;
            v.weight = 0;




            int maxProfit = 0;

            //GetBestPossibleValueForBound(n, W, p, w);
            //bestPossibleValue = bestPossibleValue;

            v.bound = bound(v, n, W, itemList);
            Q.Enqueue(new Node(v));

            while (Q.Count() != 0)
            {
                v = Q.Dequeue();

                if (v.level == -1)
                {
                    u.level = 0;
                }
                else if (v.level != (n - 1))
                {
                    u.level = v.level + 1;
                }

                u.weight = v.weight + itemList[u.level].weight;
                u.profit = v.profit + itemList[u.level].profit;
                u.path = v.path;

                u.bound = bound(u, n, W, itemList);

                if (u.weight <= W && u.profit > maxProfit)
                {
                    maxProfit = u.profit;
                    bestNode = new Node(u);
                }

                if (u.bound > maxProfit)
                {
                    Node curNodeTemp = new Node(u);
                    curNodeTemp.path += " 1";
                    Q.Enqueue(curNodeTemp);
                }

                u.weight = v.weight;
                u.profit = v.profit;

                u.bound = bound(u, n, W, itemList);

                if (u.bound > maxProfit)
                {
                    Node curNodeTemp = new Node(u);
                    curNodeTemp.path += " 0";
                    Q.Enqueue(new Node(curNodeTemp));
                }
            }
            System.Diagnostics.Debug.Write(debugInfo);
            return maxProfit;
        }

        static void GetData(string file,out int n, out int W, out int[] w, out int[] p)
        {           
            int nItems = 0;
            int knapSize = 0;
            int[] values;
            int[] weights;

            using (StreamReader sr = new StreamReader(file))
            {
                string line = sr.ReadLine();
                string[] s = line.Split();
                nItems = int.Parse(s[0]);
                knapSize = int.Parse(s[1]);
                values = new int[nItems];
                weights = new int[nItems];

                int k = 0;

                for (int kk = 0; kk < nItems; kk++)
                {
                    line = sr.ReadLine();
                    s = line.Split(new string[] { " " }, StringSplitOptions.RemoveEmptyEntries);
                    values[k] = int.Parse(s[0]);
                    weights[k] = int.Parse(s[1]);
                    k++;
                }
            }

            n = nItems;
            W = knapSize;
            w = weights;
            p = values;
        }


        /*
        static void doSolve(string file)
        {
            using (StreamReader sr = new StreamReader(file))
            {
                using (StreamWriter sw = new StreamWriter("resp.txt"))
                {
                    string line = sr.ReadLine();
                    string[] s = line.Split();
                    int nbNodes = int.Parse(s[0]);
                    int nbEdges = int.Parse(s[1]);

                    int k = 0;
                    
                    ////////////////////////
                    SolverContext context = SolverContext.GetContext();
                    context.ClearModel();
                    Model model = context.CreateModel();
                    string[] colorsList = new string[1000];
                    for (int i = 0; i < 1000; i++)
                    {
                        colorsList[i] = i.ToString();
                    }
                    //Domain colors = Domain.Enum("0", "1", "2", "3", "4", "5", "6", "7", "8", "9", "10", "11", "12", "13", "14", "15", "16", "17", "18", "19", "20", "21");
                    Domain colors = Domain.Enum(colorsList);
                    /////////////////////////////

                    List<Decision> decisionList = new List<Decision>();
                    for (int i = 0; i < nbNodes; i++)
                    {
                        Decision d = new Decision(colors, "city_" + i.ToString());
                        model.AddDecisions(d);
                        decisionList.Add(d);
                    }
                   

                    for (int kk = 0; kk < nbEdges; kk++)
                    //while (!sr.EndOfStream)
                    {
                        line = sr.ReadLine();
                        s = line.Split(new string[] { " " }, StringSplitOptions.RemoveEmptyEntries);
                        int nodeId = int.Parse(s[0]);
                        int neighbourgId = int.Parse(s[1]);
                        
                        ////////////////////////
                        model.AddConstraint("border" + kk.ToString(), decisionList[nodeId] != decisionList[neighbourgId]);

                        k++;
                        //sw.WriteLine(sr.ReadLine());
                    }

                    System.Diagnostics.Stopwatch stopWatch = new System.Diagnostics.Stopwatch();
                    stopWatch.Start();


                    




                   


                   // Decision Ontario = new Decision(colors, "Ontario");
                    ///Decision Quebec = new Decision(colors, "Quebec");
                   // Decision NB = new Decision(colors, "NB");
                   // Decision Maine = new Decision(colors, "Maine");

                   // model.AddDecisions(Ontario, Quebec, NB, Maine);

                   // model.AddConstraints("borders", Ontario != Quebec, Quebec != NB, Quebec != Maine);
                    //model.AddGoal("Goal", GoalKind.Minimize, 
                    try
                    {
                        Solution solution = context.Solve(new ConstraintProgrammingDirective());
                        while (solution.Quality != SolverQuality.Feasible)
                        {

                            //Console.WriteLine("Ontario: {0}\tQuebec: {1}\tNB: {2}\tMaine: {3}", Ontario, Quebec, NB, Maine);
                            solution.GetNext();
                        }



                        stopWatch.Stop();

                        int nbColor = 0;
                        List<string> nbColorList = new List<string>();
                        for (int i = 0; i < nbNodes; i++)
                        {
                            if (!nbColorList.Contains(decisionList[i].ToString()))
                            {
                                nbColor++;
                                nbColorList.Add(decisionList[i].ToString());
                            }
                        }

                        sw.WriteLine(nbColor.ToString() + " 1");
                        Console.WriteLine(nbColor.ToString() + " 1");
                        string ss = "";
                        for (int i = 0; i < nbNodes; i++)
                        {
                            ss += decisionList[i].ToString();
                            ss += " ";
                        }
                        sw.WriteLine(ss);
                        Console.WriteLine(ss);
                    }
                    catch
                    {
                        sw.WriteLine("4 1");
                        sw.WriteLine("0 1 2 3");

                        Console.WriteLine("4 1");
                        Console.WriteLine("0 1 2 3");
                    }
                   
                     
                      
                   // IMPLEMENT THIS
                   // sw.WriteLine(bestVal.ToString() + " 1");
                   // string ss = sol[0].ToString();
                   // for (int i = 1; i < sol.Length; i++) ss += " " + sol[i].ToString();
                   // sw.WriteLine(ss);
                    
                }
            }
        }*/

    }
}